#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 283. 移动零.py
@time: 2022/3/6 22:15
@desc: https://leetcode-cn.com/problems/move-zeroes/
> 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

1. 类似快排的思想，将非0元素尽量往前放
'''
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        j = 0
        for i in range(n):
            if nums[i]:
                nums[j] = nums[i]
                j += 1
        for k in range(j, n):
            nums[k] = 0

# 更简短的写法
class Solution02:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # j实际上是一个可能为0元素的位置，当nums[i]==0时，j就会滞后于i，停留在0元素的位置，因此当nums[i]不为0了，就可以交换位置了
        j = 0
        for i in range(n):
            if nums[i]:
                nums[j], nums[i] = nums[i], nums[j]
                j += 1